'''
Created on Nov 3, 2014

@author: azhelezny
'''
class FastaRecord:
    def __init__(self, name , dna):
        self.name = name
        self.dna = dna


inputFile = open("D:\\fasta.input")
lines = []
fileString = inputFile.readline()
while 1:
    if(not fileString):
        break
    rName = fileString.replace("\n", "").replace(">", "")
    temp = ""
    while 1:
        fileString = inputFile.readline().replace("\n", "")
        if(not fileString or fileString.count(">") != 0):
            break
        temp += fileString
    lines.append(FastaRecord(rName, temp))
inputFile.close()

def findAllSubstrings(first, second):
    lf = len(first)
    ls = len(second)
    sharedStrings = set()
    for i in range(0, lf):
        for j in range(0, ls):
            if(first[i] == second[j]):
                initialString = ''
                n = 0
                if(lf - i < ls - j):
                    n = lf - i
                else:
                    n = ls - j
                initialString += first[i]
                for k in range(1, n):
                    if(first[i + k] == second[j + k]):
                        initialString += first[i + k]
                        sharedStrings.add(initialString)
                    else:
                        break
    return sharedStrings
 
commonMotifs = findAllSubstrings(lines[0].dna, lines[1].dna)
matchedMotifs = []

for motif in (commonMotifs):
    isMatched = True
    for line in lines:
        if(line.dna.count(motif) == 0):
            isMatched = False
            break
    if(isMatched):
        matchedMotifs.append(motif)

if(len(matchedMotifs) > 0):
    maxMotif = matchedMotifs[0]
    maxLen = len(maxMotif)
    for i in range(1, len(matchedMotifs)):
        if(len(matchedMotifs[i]) > maxLen):
            maxLen = len(matchedMotifs[i])
            maxMotif = matchedMotifs[i]
print(maxMotif)
        
